\documentclass{dingjia}

\author{蛋疼的蛋蛋}
\date{\today}
\title{Database System Comcepts \\ 第六章笔记和习题}

\begin{document}

% \maketitle

\section*{形式化关系查询语言}\label{sec:orgb083c41}

\subsection*{关系代数}\label{sec:org6d1d305}

关系代数是一种过程化的语言。他包括一个运算的集合，这些运算以一个或两个关系为
输入，产生一个新的关系作为结果。

对一个关系进行运算，叫做一元运算……对两个关系进行运算，叫做二元运算。

select 选择运算选出满足给定谓词的元组。project 投影运算返回作为参数的关系，
但把某些属性排除在外。我们可以把多个关系代数运算组合成一个关系代数表达式。

要使并运算 $r \cup s$ 有意义，以下两个条件要同时成立。
\begin{itemize}
\item r 和 s 必须是同元的，即他们的属性数目必须相同。
\item r[i] s[i]的域相同。
\end{itemize}

假设 instructor 中有 n1 个元组，teaches 中有 n2 个元组。那么我们可以有 $n_1 \times n_2$ 种方式来选择元组对。找出物理系教师名字及他们所教授的课程 ID。
\begin{equation}
\Pi_{name,course\_id}(\sigma_{instructor.id = teaches.id}(\sigma_{dept\_name = "Physics"}(instructor \times teaches)))
\end{equation}

返回表达式 E，并赋给他名字 x,同时将各属性更名为 $A_1, A_2, \ldots , A_n$ 。
\begin{equation}
\rho_{x(A_1, A_2,\ldots , A_n)}(E)
\end{equation}

找出大学里老师的最高工资：首先自联结（需要更名,也可使用位置标记 $\$x$ ,但位
置标记不直观,也可能不适应未来的关系变化）,其次找出 \textbf{非} 最高工资。最
后在salary 集合里减去非最高工资。
\begin{equation}
\Pi_{instructor.salary} - \Pi_{instructor.salary}(\sigma_{instructor.salary < d.salary}(instructor \times \rho_{d}(instructor)))
\end{equation}

附加的关系代数运算，交并差和复制运算等，是属性集合上的操作，而不是关系上的。他们 \textbf{不能增加关系代数的表达能力} ，却可以 \textbf{简化} 一些常用的查询。如：
\[ r \cup s = r - (r - s) \]
\[ r \bowtie s = \Pi_{r \cup s}(\sigma_{r.{A_1} = s.{A_1} \land r.{A_2} = s.{A_2} \cup \ldots r.{A_n} = s.{A_n}}(r \times s)) \]
\[ if \qquad r \cup s = \emptyset \qquad then \qquad  r \bowtie s = r \times s \]
\[ r \bowtie_{\theta} = \sigma_{\theta}(r \times s) \]

自然连接是可结合的，如果多个关系的自然连接之间不加括号，执行顺序不确定。
$\theta$ 连接是自然连接的扩展，它使得我们可以把一个选择运算和一个笛卡尔积运
算合并为单独的一个运算。（其实就是 join \ldots{} on boolean\_expression SQL
语句）。

对关系代数查询而言，赋值必须是赋给一个临时关系变量。对永久关系的赋值形成了对数据库的修改。

外连接运算同样可以用基本关系代数运算表示。例如：
\[r ⟕ s = (r \bowtie s) \cup (r - \Pi_{r}(r \bowtie s) \times |(null,\ldots , null)|) \]

扩展的关系代数 extend relational-algebra 运算:
\begin{description}
  \item[{广义连接运算 generalized-projection}] 在投影列表中使用算数运算和字符串函数。
  \item[{聚集运算 aggregation operation}] 对值的集合使用聚集函数，如 max()
  count().聚集函数的形式通常如下：
\end{description}
\[ {}_{G_1 , G_2 , \ldots , G_n}{\mathcal{G}}_{F_1(A_1),F_2(A_2),\ldots , F_n(A_n)}(E) \] 一系列分组，一系列应用到某属性上的聚集函数

\[ {}_{dept\_name} {\mathcal{G}}_{average(salary)}(instructor) \]
对 instructor 按 dept\_name 分组聚集并计算组平均工资。

\subsection*{元组关系演算}\label{sec:org909f97d}

当书写关系代数表达式时，提供了产生查询结果的过程序列。与之相比，元组关系演
算Tuple Relational calculus是非过程化的（nonprocedural）查询语言，它只描述所
需信息，而不给出获得该信息的具体过程。

找出所有工资大于 80000 美元的老师的 ID。

\[ \{t | \exists s \in instructor (t[id] = s[id] \land s[salary] > 80000)\}
\]
它是所有满足如下条件的元组 t 的集合，关系 instructor 中存在元祖 s 使 t 和
s 在属性 id 上相等，且 s 在属性 salary 上的值大于 80000。元祖变量 t 只定义在 id
上。

元组变量t只定义在id属性上，因为表达式中只对元组变量t的id属性进行限制。

\begin{align}
\{t | \exists s \in instructor ( t[name]  = s[name] & \notag \\
\land u \in department(u[dept\_name] & = s[dept\_name] \notag \\ \land u[building]  & = "Watson"))  \}
\end{align}

找出 2009 年秋季学习开设，并且不在 2010 年春季学期开设的课程。
\begin{align}
\{t | \exists s \in section( t[course\_id]  & = s[course\_id]  \notag \\
\land s[semester] & = "Fall" \land s[year] = 2009) \notag \\
 \land \not \exists u \in section( u[course\_id]  & = t[course\_id]  \notag \\
\land u[semester] & = "Spring" \land u[year] = 2010)  \}
\end{align}

$P \Rightarrow Q \equiv \lnot P \ \lor \ Q$ 表示 P 蕴含 Q，Q 是 P 的必要条件，
P 是 Q 的充分条件，仅当 P 真 Q 假时， $P \Rightarrow Q$ 才为假 。

蛋蛋注：数据库类书籍往往说是只要 P 为真，Q必须为真。其实只是 P 蕴含 Q 为真的
一个子集而已。当P为真时，Q也为真才能使蕴含为真。

$\forall t \in r (Q(t))$,对关系 r 中的所有元组 t,Q(t)均为真。

找出所有那些选了生物（Biology）系全部课程的学生。
\begin{align}
\{|t| \exists & r \in student(r[id] = t[id]) \land  \notag \\
& \forall u \in course(u[dept\_name] = "Biology" \Rightarrow \notag \\
& \exists s \in takes( t[id] = s[id] \land s[course\_id] = u[course\_id]))\}
\end{align}
它是所有满足如下条件的学生（即(ID)上的元组 T）的集合：对关系 course 中所有的元
组 u 而言，如果 u 在 dept\_name 上的值为 Biology,则在关系 take 中一定存在一个包含该学
生 ID 以及该课程 course\_id 的元组。第一行非常重要，他意味着如果生物系没有开设任
何课程，则所有学生 ID 都满足条件。如果没有第一行，则任何一个 t 值都会符合要求。

形式化定义：元组关系演算表达式具有如下形式： ${t|P(t)}$。其中 P 是一个公式.公
式中可以出现多个元组变量。如果元组变量不被 $\exists \ or \ \forall$ 修饰，则
称为自由变量。

元组关系演算表达式可能产生一个无限的关系，于是引入了元组关系公式 P 的域
(domain)这一概念，P的域是 P 引用的所有值的集合，包括显式出现的值及 P 中关系的
所有值。

例如，$dom(t \in instructor \land t[salary] > 80000)$ 是包括 80000 和出现在
instructor 中的所有值的集合。

如果出现在表达式 $\{t|P(t)\}$ 结果中的所有值均来自 dom(P)，则我们说这个表达式是
安全的。

\subsection*{域关系演算}\label{sec:org3f5d3f6}

关系演算的另一种形式成为域关系演算 domain relational calculus,使用从属性域中
取值的域变量，而不是整个元祖的值。就像关系代数是 SQL 语言的基础一样，域关系演
算是被广泛采用的 QBE 语言的理论基础。

找出所有物理系教师的姓名,以及所有他们教授课程的 course\_id.
\begin{align}
\{ <n,c> | \exists i, a, se, y( & <i, c, a, se, y>  \in teaches \notag \\
& \land \exists d,s(<i, n, d, s> \in instructor \land d = "Physics"))\}
\end{align}

找出有在 2009 年秋季学期或者 2010 年春季学期开设的课程。
\begin{align}
\{ <c> | \exists a,s,y,b,r,t & (<c,a,s,y,b,r,t> \in section \notag \\
& \land s = "Fall" \land y = 2009) \notag \\
\lor \exists a,s,y,b,r,t & (<c,a,s,y,b,r,t> \in section \notag \\
& \land s = "Spring" \land y = 2010)\}
\end{align}

找出选修了生物系全部课程的所有学生的 ID
\begin{align}
\{ <i> | \exists n,d,tc & (<i,n,d,tc> \in student) \land \notag \\
& \forall ci, ti, dn, cr(<ci,ti,dn,cr> \in course \land dn = "Biology" \notag \\
& \qquad \qquad \qquad \Rightarrow \exists si,se,y,g(<i,ci,si,se,y,g> \in takes))\}
\end{align}
注意：如果生物系没有开设任何课程，将显示所有学生 ID。

\end{document}
